<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0//EN">
<HTML>
<HEAD>
<LINK REL=STYLESHEET TYPE="text/css" HREF="../stylesheet.css" TITLE="Style">
<META NAME="GENERATOR" CONTENT="Java2HTML Version 1.5">
<TITLE>jminusminus.NRegisterAllocator (Java2HTML)</TITLE>
</HEAD>
<BODY><TABLE id="Header" border="0" cellpadding="0" cellspacing="0" width="100%">
<tr>
<td colspan="2" width="33%">&nbsp;</td>
<td align="center" colspan="2" width="33%">
<font size="4">NRegisterAllocator.java</font>
</td>
<td align="right" colspan="2" width="33%">&nbsp;</td>
</tr>
</TABLE>
<pre ID="Classes">
<FONT ID="LN">1   </FONT><A NAME="1"></A><FONT ID="SingleLineComment">// Copyright 2013 Bill Campbell, Swami Iyer and Bahar Akbal-Delibas
<FONT ID="LN">2   </FONT><A NAME="2"></A></FONT>
<FONT ID="LN">3   </FONT><A NAME="3"></A><FONT ID="Package">package</FONT> jminusminus;
<FONT ID="LN">4   </FONT><A NAME="4"></A>
<FONT ID="LN">5   </FONT><A NAME="5"></A><FONT ID="Import">import</FONT> java.util.ArrayList;
<FONT ID="LN">6   </FONT><A NAME="6"></A><FONT ID="Import">import</FONT> java.util.BitSet;
<FONT ID="LN">7   </FONT><A NAME="7"></A>
<FONT ID="LN">8   </FONT><A NAME="8"></A><FONT ID="FormalComment">/**
<FONT ID="LN">9   </FONT><A NAME="9"></A> * A register allocator maps virtual registers (from LIR code) to physical
<FONT ID="LN">10  </FONT><A NAME="10"></A> * registers on the target machine. That there are a limited number of physical
<FONT ID="LN">11  </FONT><A NAME="11"></A> * registers makes this interesting.
<FONT ID="LN">12  </FONT><A NAME="12"></A> */</FONT>
<FONT ID="LN">13  </FONT><A NAME="13"></A>
<FONT ID="LN">14  </FONT><A NAME="14"></A><FONT ID="Public">public</FONT> <FONT ID="Abstract">abstract</FONT> <FONT ID="Class">class</FONT> NRegisterAllocator {
<FONT ID="LN">15  </FONT><A NAME="15"></A>
<FONT ID="LN">16  </FONT><A NAME="16"></A>    <FONT ID="FormalComment">/** The control flow graph for a method. */</FONT>
<FONT ID="LN">17  </FONT><A NAME="17"></A>    <FONT ID="Protected">protected</FONT> <A HREF="../jminusminus/NControlFlowGraph.java.html">NControlFlowGraph</A> cfg;
<FONT ID="LN">18  </FONT><A NAME="18"></A>
<FONT ID="LN">19  </FONT><A NAME="19"></A>    <FONT ID="FormalComment">/**
<FONT ID="LN">20  </FONT><A NAME="20"></A>     * Construct an NRegisterAllocator object given the control flow graph for
<FONT ID="LN">21  </FONT><A NAME="21"></A>     * method.
<FONT ID="LN">22  </FONT><A NAME="22"></A>     * 
<FONT ID="LN">23  </FONT><A NAME="23"></A>     * @param cfg
<FONT ID="LN">24  </FONT><A NAME="24"></A>     *            control flow graph for a method.
<FONT ID="LN">25  </FONT><A NAME="25"></A>     */</FONT>
<FONT ID="LN">26  </FONT><A NAME="26"></A>
<FONT ID="LN">27  </FONT><A NAME="27"></A>    <FONT ID="Protected">protected</FONT> NRegisterAllocator(<A HREF="../jminusminus/NControlFlowGraph.java.html">NControlFlowGraph</A> cfg) {
<FONT ID="LN">28  </FONT><A NAME="28"></A>        <FONT ID="This">this</FONT>.cfg = cfg;
<FONT ID="LN">29  </FONT><A NAME="29"></A>        <FONT ID="This">this</FONT>.cfg.intervals = <FONT ID="New">new</FONT> ArrayList&lt;<A HREF="../jminusminus/NInterval.java.html">NInterval</A>&gt;();
<FONT ID="LN">30  </FONT><A NAME="30"></A>        <FONT ID="For">for</FONT> (<FONT ID="Int">int</FONT> i = <FONT ID="IntegerLiteral">0</FONT>; i &lt; cfg.registers.size(); i++) {
<FONT ID="LN">31  </FONT><A NAME="31"></A>            <FONT ID="This">this</FONT>.cfg.intervals.add(<FONT ID="New">new</FONT> <A HREF="../jminusminus/NInterval.java.html">NInterval</A>(i, cfg));
<FONT ID="LN">32  </FONT><A NAME="32"></A>        }
<FONT ID="LN">33  </FONT><A NAME="33"></A>        <FONT ID="This">this</FONT>.cfg.maxIntervals = <FONT ID="This">this</FONT>.cfg.intervals.size();
<FONT ID="LN">34  </FONT><A NAME="34"></A>    }
<FONT ID="LN">35  </FONT><A NAME="35"></A>
<FONT ID="LN">36  </FONT><A NAME="36"></A>    <FONT ID="FormalComment">/**
<FONT ID="LN">37  </FONT><A NAME="37"></A>     * The work horse that does the allocation, implemented in the concrete
<FONT ID="LN">38  </FONT><A NAME="38"></A>     * sub-classes of NRegisterAllocator.
<FONT ID="LN">39  </FONT><A NAME="39"></A>     */</FONT>
<FONT ID="LN">40  </FONT><A NAME="40"></A>
<FONT ID="LN">41  </FONT><A NAME="41"></A>    <FONT ID="Public">public</FONT> <FONT ID="Abstract">abstract</FONT> <FONT ID="Void">void</FONT> allocation();
<FONT ID="LN">42  </FONT><A NAME="42"></A>
<FONT ID="LN">43  </FONT><A NAME="43"></A>    <FONT ID="FormalComment">/**
<FONT ID="LN">44  </FONT><A NAME="44"></A>     * Build the intervals for a control flow graph.
<FONT ID="LN">45  </FONT><A NAME="45"></A>     */</FONT>
<FONT ID="LN">46  </FONT><A NAME="46"></A>
<FONT ID="LN">47  </FONT><A NAME="47"></A>    <FONT ID="Protected">protected</FONT> <FONT ID="Void">void</FONT> buildIntervals() {
<FONT ID="LN">48  </FONT><A NAME="48"></A>        <FONT ID="This">this</FONT>.computeLocalLiveSets();
<FONT ID="LN">49  </FONT><A NAME="49"></A>        <FONT ID="This">this</FONT>.computeGlobalLiveSets();
<FONT ID="LN">50  </FONT><A NAME="50"></A>        <FONT ID="For">for</FONT> (<FONT ID="Int">int</FONT> i = cfg.basicBlocks.size() - <FONT ID="IntegerLiteral">1</FONT>; i &gt;= <FONT ID="IntegerLiteral">0</FONT>; i--) {
<FONT ID="LN">51  </FONT><A NAME="51"></A>            NBasicBlock currBlock = cfg.basicBlocks.get(i);
<FONT ID="LN">52  </FONT><A NAME="52"></A>            <FONT ID="If">if</FONT> (currBlock.lir.size() == <FONT ID="IntegerLiteral">0</FONT>) {
<FONT ID="LN">53  </FONT><A NAME="53"></A>                <FONT ID="Continue">continue</FONT>;
<FONT ID="LN">54  </FONT><A NAME="54"></A>            }
<FONT ID="LN">55  </FONT><A NAME="55"></A>            <FONT ID="Int">int</FONT> blockStart = currBlock.lir.get(<FONT ID="IntegerLiteral">0</FONT>).id;
<FONT ID="LN">56  </FONT><A NAME="56"></A>            <FONT ID="Int">int</FONT> blockEnd = currBlock.lir.get(currBlock.lir.size() - <FONT ID="IntegerLiteral">1</FONT>).id;
<FONT ID="LN">57  </FONT><A NAME="57"></A>            BitSet liveOut = currBlock.liveOut;
<FONT ID="LN">58  </FONT><A NAME="58"></A>            <FONT ID="For">for</FONT> (<FONT ID="Int">int</FONT> idx = liveOut.nextSetBit(<FONT ID="IntegerLiteral">0</FONT>); idx &gt;= <FONT ID="IntegerLiteral">0</FONT>; idx = liveOut
<FONT ID="LN">59  </FONT><A NAME="59"></A>                    .nextSetBit(idx + <FONT ID="IntegerLiteral">1</FONT>)) {
<FONT ID="LN">60  </FONT><A NAME="60"></A>                cfg.intervals.get(idx).addOrExtendNRange(
<FONT ID="LN">61  </FONT><A NAME="61"></A>                        <FONT ID="New">new</FONT> NRange(blockStart, blockEnd));
<FONT ID="LN">62  </FONT><A NAME="62"></A>            }
<FONT ID="LN">63  </FONT><A NAME="63"></A>            <FONT ID="For">for</FONT> (<FONT ID="Int">int</FONT> j = currBlock.lir.size() - <FONT ID="IntegerLiteral">1</FONT>; j &gt;= <FONT ID="IntegerLiteral">0</FONT>; j--) {
<FONT ID="LN">64  </FONT><A NAME="64"></A>                <FONT ID="Int">int</FONT> currLIRid = currBlock.lir.get(j).id;
<FONT ID="LN">65  </FONT><A NAME="65"></A>                <A HREF="../jminusminus/NRegister.java.html">NRegister</A> output = currBlock.lir.get(j).write;
<FONT ID="LN">66  </FONT><A NAME="66"></A>                <FONT ID="If">if</FONT> (output != <FONT ID="Null">null</FONT>) {
<FONT ID="LN">67  </FONT><A NAME="67"></A>                    cfg.intervals.get(output.number).newFirstRangeStart(
<FONT ID="LN">68  </FONT><A NAME="68"></A>                            currLIRid);
<FONT ID="LN">69  </FONT><A NAME="69"></A>                    cfg.intervals.get(output.number).addUsePosition(currLIRid,
<FONT ID="LN">70  </FONT><A NAME="70"></A>                            InstructionType.write);
<FONT ID="LN">71  </FONT><A NAME="71"></A>                }
<FONT ID="LN">72  </FONT><A NAME="72"></A>                ArrayList&lt;<A HREF="../jminusminus/NRegister.java.html">NRegister</A>&gt; inputs = currBlock.lir.get(j).reads;
<FONT ID="LN">73  </FONT><A NAME="73"></A>                <FONT ID="For">for</FONT> (<A HREF="../jminusminus/NRegister.java.html">NRegister</A> reg : inputs) {
<FONT ID="LN">74  </FONT><A NAME="74"></A>                    cfg.intervals.get(reg.number).addOrExtendNRange(
<FONT ID="LN">75  </FONT><A NAME="75"></A>                            <FONT ID="New">new</FONT> NRange(blockStart, currLIRid));
<FONT ID="LN">76  </FONT><A NAME="76"></A>                    cfg.intervals.get(reg.number).addUsePosition(currLIRid,
<FONT ID="LN">77  </FONT><A NAME="77"></A>                            InstructionType.read);
<FONT ID="LN">78  </FONT><A NAME="78"></A>                }
<FONT ID="LN">79  </FONT><A NAME="79"></A>            }
<FONT ID="LN">80  </FONT><A NAME="80"></A>        }
<FONT ID="LN">81  </FONT><A NAME="81"></A>    }
<FONT ID="LN">82  </FONT><A NAME="82"></A>
<FONT ID="LN">83  </FONT><A NAME="83"></A>    <FONT ID="FormalComment">/**
<FONT ID="LN">84  </FONT><A NAME="84"></A>     * Iterate through a list of basic blocks in order, and sets their liveUse
<FONT ID="LN">85  </FONT><A NAME="85"></A>     * and liveDef BitSet fields to represent the appropriate virtual registers
<FONT ID="LN">86  </FONT><A NAME="86"></A>     * that are locally defined to each block. It works internally with the
<FONT ID="LN">87  </FONT><A NAME="87"></A>     * cfg's basicBlock structure.
<FONT ID="LN">88  </FONT><A NAME="88"></A>     */</FONT>
<FONT ID="LN">89  </FONT><A NAME="89"></A>
<FONT ID="LN">90  </FONT><A NAME="90"></A>    <FONT ID="Private">private</FONT> <FONT ID="Void">void</FONT> computeLocalLiveSets() {
<FONT ID="LN">91  </FONT><A NAME="91"></A>        <FONT ID="For">for</FONT> (NBasicBlock block : cfg.basicBlocks) {
<FONT ID="LN">92  </FONT><A NAME="92"></A>            block.liveUse = <FONT ID="New">new</FONT> BitSet(cfg.registers.size());
<FONT ID="LN">93  </FONT><A NAME="93"></A>            block.liveDef = <FONT ID="New">new</FONT> BitSet(cfg.registers.size());
<FONT ID="LN">94  </FONT><A NAME="94"></A>            <FONT ID="For">for</FONT> (<A HREF="../jminusminus/NLIRInstruction.java.html">NLIRInstruction</A> inst : block.lir) {
<FONT ID="LN">95  </FONT><A NAME="95"></A>                <FONT ID="For">for</FONT> (<A HREF="../jminusminus/NRegister.java.html">NRegister</A> reg : inst.reads) {
<FONT ID="LN">96  </FONT><A NAME="96"></A>                    <FONT ID="If">if</FONT> (!(block.liveDef.get(reg.number()))) {
<FONT ID="LN">97  </FONT><A NAME="97"></A>                        block.liveUse.set(reg.number());
<FONT ID="LN">98  </FONT><A NAME="98"></A>                    }
<FONT ID="LN">99  </FONT><A NAME="99"></A>                }
<FONT ID="LN">100 </FONT><A NAME="100"></A>                <FONT ID="If">if</FONT> (inst.write != <FONT ID="Null">null</FONT>) {
<FONT ID="LN">101 </FONT><A NAME="101"></A>                    block.liveDef.set(inst.write.number());
<FONT ID="LN">102 </FONT><A NAME="102"></A>                }
<FONT ID="LN">103 </FONT><A NAME="103"></A>            }
<FONT ID="LN">104 </FONT><A NAME="104"></A>        }
<FONT ID="LN">105 </FONT><A NAME="105"></A>    }
<FONT ID="LN">106 </FONT><A NAME="106"></A>
<FONT ID="LN">107 </FONT><A NAME="107"></A>    <FONT ID="FormalComment">/**
<FONT ID="LN">108 </FONT><A NAME="108"></A>     * Iterate through a list of basic blocks in reverse order, and sets their
<FONT ID="LN">109 </FONT><A NAME="109"></A>     * lliveIn and liveOut bit sets to reflect global use-def information. It
<FONT ID="LN">110 </FONT><A NAME="110"></A>     * works internally with the cfg's basicBlock structure.
<FONT ID="LN">111 </FONT><A NAME="111"></A>     */</FONT>
<FONT ID="LN">112 </FONT><A NAME="112"></A>
<FONT ID="LN">113 </FONT><A NAME="113"></A>    <FONT ID="Private">private</FONT> <FONT ID="Void">void</FONT> computeGlobalLiveSets() {
<FONT ID="LN">114 </FONT><A NAME="114"></A>        <FONT ID="Boolean">boolean</FONT> changed = <FONT ID="False">false</FONT>;
<FONT ID="LN">115 </FONT><A NAME="115"></A>        <FONT ID="For">for</FONT> (NBasicBlock b : cfg.basicBlocks) {
<FONT ID="LN">116 </FONT><A NAME="116"></A>            b.liveOut = <FONT ID="New">new</FONT> BitSet(cfg.registers.size());
<FONT ID="LN">117 </FONT><A NAME="117"></A>        }
<FONT ID="LN">118 </FONT><A NAME="118"></A>
<FONT ID="LN">119 </FONT><A NAME="119"></A>        <FONT ID="SingleLineComment">// note: we only check for changes in liveOut.
<FONT ID="LN">120 </FONT><A NAME="120"></A></FONT>        <FONT ID="Do">do</FONT> {
<FONT ID="LN">121 </FONT><A NAME="121"></A>            changed = <FONT ID="False">false</FONT>;
<FONT ID="LN">122 </FONT><A NAME="122"></A>            <FONT ID="For">for</FONT> (<FONT ID="Int">int</FONT> i = cfg.basicBlocks.size() - <FONT ID="IntegerLiteral">1</FONT>; i &gt;= <FONT ID="IntegerLiteral">0</FONT>; i--) {
<FONT ID="LN">123 </FONT><A NAME="123"></A>                NBasicBlock currBlock = cfg.basicBlocks.get(i);
<FONT ID="LN">124 </FONT><A NAME="124"></A>                BitSet newLiveOut = <FONT ID="New">new</FONT> BitSet(cfg.registers.size());
<FONT ID="LN">125 </FONT><A NAME="125"></A>                <FONT ID="For">for</FONT> (NBasicBlock successor : currBlock.successors) {
<FONT ID="LN">126 </FONT><A NAME="126"></A>                    newLiveOut.or(successor.liveIn);
<FONT ID="LN">127 </FONT><A NAME="127"></A>                }
<FONT ID="LN">128 </FONT><A NAME="128"></A>                <FONT ID="If">if</FONT> (!currBlock.liveOut.equals(newLiveOut)) {
<FONT ID="LN">129 </FONT><A NAME="129"></A>                    currBlock.liveOut = newLiveOut;
<FONT ID="LN">130 </FONT><A NAME="130"></A>                    changed = <FONT ID="True">true</FONT>;
<FONT ID="LN">131 </FONT><A NAME="131"></A>                }
<FONT ID="LN">132 </FONT><A NAME="132"></A>                currBlock.liveIn = (BitSet) currBlock.liveOut.clone();
<FONT ID="LN">133 </FONT><A NAME="133"></A>                currBlock.liveIn.andNot(currBlock.liveDef);
<FONT ID="LN">134 </FONT><A NAME="134"></A>                currBlock.liveIn.or(currBlock.liveUse);
<FONT ID="LN">135 </FONT><A NAME="135"></A>            }
<FONT ID="LN">136 </FONT><A NAME="136"></A>        } <FONT ID="While">while</FONT> (changed);
<FONT ID="LN">137 </FONT><A NAME="137"></A>    }
<FONT ID="LN">138 </FONT><A NAME="138"></A>
<FONT ID="LN">139 </FONT><A NAME="139"></A>}
<FONT ID="LN">140 </FONT><A NAME="140"></A></pre>
</BODY>
</HTML>